# -*- coding: utf-8 -*-

"""72. 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符

示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：
0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成"""

class Solution:
    """
    这道题一开始完全无头绪，不知道怎么下手。经过仔细思考，发现一种方法，首先找到两个字符串的最大子序列，然后对一种最大子序列，对两个字符串分段，比较两个分段的长短决定是替换还是插入；
    最后删掉多余的字符，包括上一步中插入的字符。实际编程的时候，在插入、替换、操作的时候，可以只看长度，不看具体字符串。
    这样也能实现，也用到了动态规划（在找最大公共子序列部分），但是在后续的操作中略显麻烦。所以看题解。
    题解就简省很多，直接从问题源头动态规划，定义 f(i, j) 为计算字符串 word1[0:i] vs word2[0:j] 部分需要编辑的最少操作数。则
    递归定义：
        f(i,j) = f(i-1, j-1)                                    # 当 word1[i] == word2[j] 时
        f(i,j) = min(f(i-1, j-1), f(i-1, j), f(i, j-1)) + 1     # 当 word1[i] != word2[j] 时，分别是替换，删除，插入
    递归基础：
        由递归可见，是一个矩阵，且基础为首行首列的直角。
        f(0,0) = word1[0] != word1[0]       # 相等就是0，不等就替换
        f(0,j+1) = f(0,j) if word1[0] == word2[j+1] else f(0,j) + 1               # 首行判断自增，逐渐删除
        f(i+1,0) = f(i,0) if word1[i+1] == word2[0] else f(i,0) + 1               # 首列判断自增，逐渐插入
        -------------------------------------------------------------
        上面基础有问题，f(e, ee) = 1, f(e, eee) = 2，它们都满足 word1[0] == word2[j]
        所以当 word1[0] == word2[j] 时，应该考虑等于 f(e, eee) = f('', ee)
        所以在两个字符串前添加一个空串辅助字符。
    """
    def minDistance(self, word1: str, word2: str) -> int:
        word1, word2 = ' ' + word1, ' ' + word2
        m, n = len(word1), len(word2)
        if m == 0:
            return n
        if n == 0:
            return m

        dp = [[0 for _ in range(m)] for _ in range(n)]

        dp[0][0] = 0

        i = 1
        while i < m:
            dp[0][i] = dp[0][i-1] + 1
            i += 1
        j = 1
        while j < n:
            dp[j][0] = dp[j-1][0] + 1
            j += 1

        j = 1
        while j < n:
            i = 1
            while i < m:
                if word1[i] == word2[j]:
                    dp[j][i] = dp[j-1][i-1]
                else:
                    dp[j][i] = min(dp[j-1][i-1], dp[j][i-1], dp[j-1][i]) + 1
                i += 1
            j += 1

        # for foo in dp:
        #     print(foo)

        return dp[-1][-1]


if __name__ == '__main__':
    rs = Solution().minDistance(word1 = "pneumonoultramicroscopicsilicovolcanoconiosis", word2 = "ultramicroscopically")
    print(rs)
